package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.Greedy;

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;

/**
 * 先安排高个的.
 * Input:
 * {{7,0},{4,4},{7,1},{5,0},{6,1},{5,2}}
 * sorted:
 * [[4, 4], [5, 0], [5, 2], [6, 1], [7, 0], [7, 1]]
 * <p>
 * Output:
 * {{5,0},{7,0},{5,2},{6,1},{4,4},{7,1}}
 *
 * @author tzp
 * @since 2020/10/17
 */
public class LC406 implements Greedy {
    public int[][] reconstructQueue(int[][] people) {
        if (people == null || people.length <= 1) return people;
        int[][] peopleSorted = Arrays.stream(people)
                .sorted(Comparator.comparingInt((int[] o) -> o[0]).reversed()
                        .thenComparingInt((int[] o) -> o[1]))
                .toArray(int[][]::new);
        LinkedList<int[]> list = new LinkedList<>();
        for (int i = 0; i < peopleSorted.length; i++) {
            list.add(peopleSorted[i][1], peopleSorted[i]);
        }
        return list.toArray(new int[0][]);
    }

    public static void main(String[] args) {
        System.out.println(Arrays.deepToString(new LC406()
                .reconstructQueue(new int[][]{{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}})));
    }
}
